package com.yoshino.leetcode.improve40.twentythird;

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int peakIndexInMountainArray(int[] arr) {
        // 局部具有排序性,二分法：顶点两端的值一定比该点小
        // 一定不要在两端开始遍历：首先两端不可能为顶点，其次可能出现出界问题 mid - 1
        int left = 1, right = arr.length - 2, mid;
        while (left <= right) {
            mid = left + (right - left) >> 1;
            if (arr[mid] > arr[mid - 1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    public int singleNonDuplicate(int[] nums) {
        // 二分查找：
        // 假定左部分已经出现单个数字
        // mid 为 奇，mid != mid - 1 != mid ^ 1
        // mid 为 偶，mid != mid + 1 != mid ^ 1
        // 使用 异或 mid ^ 1
        int left = 0, right = nums.length - 1, mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (nums[mid] == nums[mid ^ 1]) {
                // 在右边
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }

}